package source.binaryTree;

import org.junit.Test;

import java.math.BigDecimal;
import java.util.*;

public class BinaryTree {
    /**
     * 二叉树的最大深度
     * <p>
     * 给定一个二叉树 root ，返回其最大深度。
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     *
     * @param root 根节点
     * @return 二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        else
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

    }

    /**
     * 相同的树
     * <p>
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p p = [1,2,1],
     * @param q q = [1,1,2]
     * @return false
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        else if (p == null || q == null)
            return false;
        else if (p.val != q.val) {
            return false;
        } else
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /**
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     *
     * @param root root = [4,2,7,1,3,6,9]
     * @return [4, 7, 2, 9, 6, 3, 1]
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.right = left;
        root.left = right;
        return root;
    }

    /**
     * 对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     * @param root 二叉树根节点
     * @return 是否轴对称
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return check(root.left, root.right);
    }

    boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left == null || right == null)
            return false;
        return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    }

    private Map<Integer, Integer> indexMap;


    /**
     * 从前序与中序遍历序列构造二叉树
     * <p>
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * 提示:
     * 1 <= preorder.length <= 3000
     * inorder.length == preorder.length
     * -3000 <= preorder[i], inorder[i] <= 3000
     * preorder 和 inorder 均 无重复 元素
     * inorder 均出现在 preorder
     * preorder 保证 为二叉树的前序遍历序列
     * inorder 保证 为二叉树的中序遍历序列
     *
     * @param preorder preorder = [3,9,20,15,7],
     * @param inorder  inorder = [9,3,15,20,7]
     * @return [3, 9, 20, null, null, 15, 7]
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i++)
            indexMap.put(inorder[i], i);
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right)
            return null;

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }


    HashMap<Integer, Integer> map = new HashMap<>();

    /**
     * 从中序与后序遍历序列构造二叉树
     *
     * @param inorder   inorder = [9,3,15,20,7],
     * @param postorder postorder = [9,15,7,20,3]
     * @return [3, 9, 20, null, null, 15, 7]
     */
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return myBuildTree(postorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode myBuildTree(int[] postorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
        if (postorder_left > postorder_right)
            return null;
        // 创建根节点
        TreeNode root = new TreeNode(postorder[postorder_right]);

        int place = map.get(postorder[postorder_right]); // 根节点在中序遍历序列中的位置
        // 获取右子树长度
        int right_length = inorder_right - place;

        root.left = myBuildTree(postorder, postorder_left, postorder_right - right_length - 1, inorder_left, place - 1);
        root.right = myBuildTree(postorder, postorder_right - right_length, postorder_right - 1, place + 1, inorder_right);
        return root;
    }

    @Test
    public void testQueue() {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(null);
        System.out.println(queue.size());
    }

    public static void printVariable(String... args) {
        for (String s : args) {
            System.out.println(s);
        }
    }

    public static void printVariable(String arg1, String arg2) {
        System.out.println(arg1 + arg2);
    }

    //    public static void printVariable(String[] strs){
//
//    }
    @Test
    public void testVariable() {
        printVariable("a", "b");
        printVariable("a", "b", "c", "d");
        float a = 2.0f - 1.9F;
        float b = 0.1f;
        System.out.println(a);
        BigDecimal bigDecimal1 = new BigDecimal("3.1415");
        BigDecimal bigDecimal2 = new BigDecimal("3.1400005");
        System.out.println(bigDecimal1.add(bigDecimal2));

    }

    public Node connect(Node root) {
        Deque<Node> queue = new LinkedList<>();
        if (root == null)
            return null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            Node pre = null;
            Node cur = null;
            for (int i = 0; i < n; i++) {
                cur = queue.poll();
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
                if (pre == null) {
                    pre = cur;
                    continue;
                }
                pre.next = cur;
                pre = cur;
            }
        }
        return root;
    }

    /**
     * 二叉树展开为链表
     * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     *
     * @param root root = [1,2,5,3,4,null,6]
     */
    public void flatten(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        if (root != null)
            stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
            if (pre != null) {
                pre.right = node;
                pre.left = null;
            }
            pre = node;
        }
    }

    /**
     * 路径总和
     *
     * @param root      二叉树的根节点 root
     * @param targetSum 整数 targetSum
     * @return 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    /**
     * 求根节点到叶节点数字之和
     * <p>
     * 每条从根节点到叶节点的路径都代表一个数字：
     * 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
     * 计算从根节点到叶节点生成的 所有数字之和 。
     * 叶节点 是指没有子节点的节点。
     *
     * @param root 二叉树的根节点 root, 树中每个节点都存放有一个 0 到 9 之间的数字
     * @return 根节点到叶节点数字之和
     */
    public int sumNumbers(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) return 0;
        int sum = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left == null && cur.right == null)
                sum += cur.val;
            if (cur.left != null) {
                cur.left.val = cur.val * 10 + cur.left.val;
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                cur.right.val = cur.val * 10 + cur.right.val;
                queue.offer(cur.right);
            }
        }
        return sum;
    }

    int maxSum = Integer.MIN_VALUE;

    /**
     * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。
     * 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     * 路径和 是路径中各节点值的总和。
     *
     * @param root 二叉树的根节点 root
     * @return 最大路径和
     */
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null)
            return 0;

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

    /**
     * 完全二叉树的节点个数
     *
     * @param root 根节点
     * @return 节点个数
     */
    public int countNodes(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return 0;
        int result = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            result++;
            if (cur.left != null)
                queue.offer(cur.left);
            if (cur.right != null)
                queue.offer(cur.right);
        }
        return result;
    }

    private TreeNode result = null;

    /**
     * 二叉树的最近公共祖先
     * <p>
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
     * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return result;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean l = dfs(root.left, p, q);
        boolean r = dfs(root.right, p, q);
        if (l && r || (root.val == p.val || root.val == q.val) && (l || r)) {
            result = root;
            return true;
        }
        return l || r || root.val == p.val || root.val == q.val;
    }

    /**
     * 二叉树的右视图
     *
     * @param root 给定一个二叉树的 根节点 root，
     * @return 想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return list;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                TreeNode cur = queue.poll();
                if (i == length - 1) {
                    list.add(cur.val);
                }
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
        return list;
    }

    /**
     * 二叉树的层平均值
     * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。
     *
     * @param root 非空二叉树的根节点
     * @return 以数组的形式返回每一层节点的平均值
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return list;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            double sum = 0;
            for (int i = 0; i < len; i++) {
                TreeNode cur = queue.poll();
                sum += cur.val;
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
            double d = sum / len;
            list.add(Double.valueOf(d));
        }
        return list;
    }

    /**
     * 二叉树的层序遍历
     *
     * @param root 给你二叉树的根节点 root ，
     * @return 返回其节点值的 层序遍历 。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return list;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            List<Integer> iList = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode cur = queue.poll();
                iList.add(cur.val);
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
            list.add(iList);
        }
        return list;
    }

    /**
     * 二叉树的锯齿形层序遍历
     *
     * @param root 给你二叉树的根节点 root ，
     * @return 返回其节点值的 锯齿形层序遍历 。
     * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null)
            queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int len = queue.size();
            List<Integer> iList = new ArrayList<>();

            for (int i = 0; i < len; i++) {
                TreeNode cur = queue.poll();
                if (flag)
                    iList.add(cur.val);
                else
                    iList.add(0, cur.val);
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
            flag = !flag;
            list.add(iList);
        }
        return list;
    }

    int pre = -1;
    int ans;

    /**
     * 二叉搜索树的最小绝对差
     *
     * @param root 给你一个二叉搜索树的根节点 root ，
     * @return 返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
     */
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        preOrder(root);
        return ans;
    }

    public void preOrder(TreeNode node) {
        if (node == null)
            return;
        preOrder(node.left);
        if (pre == -1)
            pre = node.val;
        else {
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
        }
        preOrder(node.right);
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String string = scanner.nextLine();
        Integer i = Integer.parseInt(string);
        System.out.println(i.getClass() +":"+ i);
    }
}




